\section{Utility and Value} % (fold)
\label{sec:utility}
\subsection{Standard Model} % (fold)
\label{sub:standard_model}
We define a fairly simple method for assigning value to nodes, based around the idea that any connection between two nodes (no matter how distant) has a value of 1. That value is divided evenly amongst all nodes that appear on \emph{some} shortest path between the two nodes. Some examples are given below.

\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    \node [normalnode,label=above right:$\frac{1}{2}+\frac{1}{2}+\frac{1}{3}$]
      (1) {1};
    \node [normalnode,label=below left:$\frac{1}{2}+\frac{1}{3}$,
      below left=of 1] (2) {2};
    \node [normalnode,label=below right:$\frac{1}{2}+\frac{1}{3}$,
      below right=of 1] (3) {3};
    
    \draw (2) -- (1) -- (3);
  \end{tikzpicture}
  \caption{Assigning value to nodes on a very simple network.
  \label{fig:util_ex_1}}
\end{figure}

In our first example, there are three connected pairs: $(1, 2)$, $(1, 3)$, and $(2, 3)$. There are unique shortest paths between all of these pairs: $(1, 2)$ and $(1, 3)$ have paths that use two nodes, and $(1, 3)$ has a path that uses three nodes. In our system, value is split amongst all nodes that appear on some shortest path between a pair of nodes. So, each node on the $(1, 2)$ and $(1, 3)$ paths receive $+\frac{1}{2}$ value, as there are two nodes on each of those paths. Likewise, each node on the $(1, 3)$ path receives $+\frac{1}{3}$ value. The total values for each node are shown in figure \ref{fig:util_ex_1}.

\begin{figure}[ht]
  \centering
  \begin{tikzpicture}
    \node [matrix,column sep=10mm]
    {
      & \node [normalnode,
        label=above:$\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}$]
        (2) {2}; & \\
      
      \node [normalnode,
          label=above left:$\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}$]
          (1) {1};
      & &
      \node [normalnode,
        label=below right:$\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}$]
        (4) {4}; \\
      
      & \node [normalnode,
        label=below:$\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}$]
        (3) {3}; & \\
    };
    
    \draw (1) -- (2) -- (4); \draw (1) -- (3) -- (4);
  \end{tikzpicture}
  \caption{Assigning value when there are multiple shortest paths between a pair of nodes.
  \label{fig:util_ex_2}}
\end{figure}

Figure \ref{fig:util_ex_2} presents a more complicated example. The graph itself is not very complex; in fact, since it is perfectly symmetrical, all nodes receive the same value. But the expressions for the nodes' value contain $\frac{1}{4}$ components, and there is no shortest path between any two nodes in the graph that uses four nodes. What is happening?

Consider the pair of nodes $(1, 4)$. There are two paths between them that have the shortest possible length: $(1 \rightarrow 2 \rightarrow 4)$ and $(1 \rightarrow 3 \rightarrow 4)$. As always, value for this pair is divided amongst all nodes that appear on these paths; i.e., amongst the set $\{1, 2, 4\} \cup \{1, 3, 4\}$. But notice that nodes $1$ and $4$ appear twice in this union, and the set actually only contains four nodes: $\{1, 2, 3, 4\}$. Value is divided equally amongst these four nodes, so each receives $+\frac{1}{4}$ value. The same process occurs for the $(2, 3)$ pair.

Note that nodes $1$ and $4$ in particular receive less value for their connection than they would if there were only one shortest path between them. Some of the implications of this are discussed in section \ref{ssub:tails}.

\subsubsection{Formal Definition} % (fold)
\label{ssub:value_formal_definition}
In section \ref{sub:model_formal_definition}, we introduced the function $u_a$ for the utility of any node $a$ in terms of a function $v_a$, $ u_a = v_a - c_a$, where $v_a$ is the value gained by $a$ from all connections it is involved in, and $c_a$ is the cost it incurs.

The value function is made up of the value derived from having a connection to other nodes and the value derived from being a middleman on a path between other nodes. In our standard value function, for every path between any two nodes the contribution to $v_a$ is the inverse of the number of nodes on all shortest paths between those two nodes. On any path, the middleman node receives the same value from that path as the nodes actually being connected.

% subsubsection value_formal_definition (end)

% subsection standard_model (end)

\subsection{Alternate Value Functions} % (fold)
\label{sub:alternate_functions}
Alternate value functions were motivated by an unnatural result from the standard value function. Nodes can certainly lose utility by adding an edge (because that edge will have some cost), but because value is split evenly amongst all nodes who appear on any shortest path between a pair of nodes, it is possible to lose \emph{value} by adding an edge when it makes an existing shortest path redundant. The goal of this model was to emulate human interactions, but losing value for adding a friendship is contradictory to this goal.

\subsubsection{Infantile Model}
\label{subs:infantile}
In this model there is no middle-man benefit at all (so $v(a) =v_E(a)$). Value is only accrued by having a path to another node. The value for this pair of nodes is calculated by rewarding each node in the pair with $\frac{1}{k}$ where $k$ is the number of nodes on a shortest path between the two nodes. This utility model produces many disconnected graphs that are stable on some $\alpha$ as can be seen in \autoref{sec:catalog_of_stable_graphs}. Intuitively, this result is undesirable because a node should greatly benefit from being connected to all other nodes and, therefore should form a connection to a disconnected component in most situations. (Connectivity is one of the goals for our model, as explained in section \ref{sub:model_goals}).

\subsubsection{Complex Model}
\label{subs:complex}
This model is identical to the standard model except for its handling of multiple shortest paths. In the complex model, the value accrued from a connection between nodes $a$ and $b$ can be different for $a$ and $b$ and all intermediate nodes. Nodes $a$ and $b$ are always awarded $\frac{1}{k}$ where $k$ is the number of nodes on a shortest path. Intermediate nodes are awarded $\frac{1-\frac{2}{k}}{r}$ where $r$ is the total number of nodes on all shortest paths, not including $a$ and $b$. Note that the total value generated from a connection between $a$ to $b$ is one, just like in the standard model. The benefit of this model is that it maintains the value of a connection for the endpoint nodes independent of multiple shortest paths.

Tails (see section \ref{ssub:tails}) in the standard model are often the result of the node on the tail losing \emph{value} when it makes another edge. Losing not just utility, but value from a new edge does not make sense for a model of a social network. One goal of the complex model was to ensure that complete graphs with one or more single node tails were not stable on any cost $\alpha$. However, the actual results from the complex model are more complicated. A single node connected to a otherwise complete graph is still stable under the complex model, but the stable $\alpha$ range is reduced from $\frac{1}{2} + \frac{n-3}{4} - \frac{n-2}{3} \leq \alpha \leq \frac{1}{2} - \frac{1}{n-1}$ in the standard model to $\alpha = \frac{1}{6}$ in the complex model (see appendix \ref{sec:single_tail_graph_stability}). Note that $\frac{1}{6} = \frac{1}{2} - \frac{1}{3}$, which is the change in value experienced by the tail node if it makes the edge. Additionally, many graphs that were not stable for any $\alpha$ with the standard utility function are stable for $\alpha=\frac{1}{6}$ with the complex utility function. Ultimately this is a better result than the standard model because problematic graphs appear only when $\alpha = \frac{1}{6}$ and not on nearly all $\alpha$ from zero to $\frac{1}{2}$.
% subsection alternate_functions (end)
% section utility (end)
